package com.sufen.seckill.study.LeetCode;

/**
 * @Author sufen
 * @Date 2021/11/12 17:32
 * @Version 1.0
 * 功能描述：
 */
public class b_110_平衡二叉树 {
    static class TreeNode{
        int val;
        TreeNode left=null;
        TreeNode right=null;
        public TreeNode(int val){
            this.val=val;
        }
    }

    public static void main(String[] args) {
        TreeNode t1=new TreeNode(1);
        TreeNode t2=new TreeNode(2);
        TreeNode t3=new TreeNode(3);
        TreeNode t4=new TreeNode(4);
        TreeNode t5=new TreeNode(5);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;

        TreeNode t6=new TreeNode(6);
        t4.left=t6;

        System.out.println(isBalanced(t1));
        /*
             1
          2    3
        4  5 [] []
      6
         */
    }
    public static boolean isBalanced(TreeNode root){
        return dfs(root)==-1?false:true;
    }
    public static int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);

        if(Math.abs(left-right)>=2||left==-1||right==-1){
            return -1;
        }

        return Math.max(left,right)+1;
    }
}
